home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part2 / 12562 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  2.0 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Finite State Machine
  5. Date: 1 Apr 1996 11:53:56 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4jpc8kINN3oo@keats.ugrad.cs.ubc.ca>
  8. References: <8BDC44A.02C7002D6C.uuout@sourcebbs.com> <4joh9v$jct@news.acns.nwu.edu>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <4joh9v$jct@news.acns.nwu.edu>,
  12. Usman Muzaffar <muzaffar@casbah.acns.nwu.edu> wrote:
  13. >In article <8BDC44A.02C7002D6C.uuout@sourcebbs.com>,
  14. >DAVID MOHORN <david.mohorn@sourcebbs.com> wrote:
  15. >>Whats a Finite State Machine (FSM)?
  16. >>
  17. >
  18. >First of all, this question has absolutely nothing to do with C, 
  19. >so redirect follow-ups to comp.theory whatever.
  20. >
  21. >An FSM is a mathematical construct. Technically, it's an ordered
  22. >quintuple consisting of a set of states, a start state, a transition
  23. >function, an alphabet, and a set of finishing states.
  24. >
  25. >Without getting into all the gory details: it's basically a mathematical
  26. >description of a very, simple computer that is a very useful model
  27. >for studying what kind of problems can be solved and how.
  28.  
  29. Heh. I think you may have mixed that up with Turing Machine.
  30.  
  31. Most computers are FSM's only in the sense that memory is limited, but the
  32. abstract FSM is a pretty useless model for studying what kinds of problems are
  33. can be practically solved.
  34.  
  35. Many problems that _are_ computable on small data sets can't easily be modelled
  36. by FSM's. 
  37.  
  38. You can't design a parser for a nested grammar with an FSM, for example.
  39. Actually you could, but you would have to have a large number of states
  40. explicitly defined, to account for the deepest possible nesting: not a suitable
  41. way to approach the problem, when you can just pretend that your computer is a
  42. TM for sufficiently small data sets. The structure of actual, real-world
  43. reflects that. A C program, for instance, is _conceptually_ portable to a
  44. machine that has an infinite stack depth, infinite malloc() space, and so
  45. forth.
  46. -- 
  47.  
  48.